P6753 [BalticOI 2013 Day1] Ball Machine

题意

给你一个树，每次从根节点放一个求，如果其子节点有空这个球会向下滚，若有多个节点为空则找儿子中以子树内编号的最小值为优先级从小到大找第一个为空的位置滚。

有两种操作，第一种插入若干个球，输出最后一个球到的节点编号；第二种删除一个位置，此时若有可以向下滚的球那么这个球就会滚，输出有多少个球滚了。

保证数据合法。

思路

首先我们思考只有1操作的情况。

对于1操作，球加入的顺序为按照以子树内编号的最小值为优先级的后序遍历 dfs 序。我们得到了 40pts。

对于2操作，删掉一个球后答案一定是其所有祖先中有球的位置的个数。原因显然，因为删球前一定是最佳状态，即没有球能动，所以删掉这个球后只有其祖先会向下移动并且一定会向下移动。

发现祖先有球的段一定是连续的，于是我们就可以用倍增找到最浅的有球的祖先，并且顺便输出答案。

但是2操作后会把父亲节点删去。注意这时候删去的节点并非最后加入的点。而且下一次加入球时会找 dfs 序最小的。这时候我们就需要一些东西比如 stl 的 vector / priority_queue / set 进行维护了。

还有最最最重要的一点！对于操作1，我们是依次一个一个加入的，这样的时间复杂度为什么是正确的？

显然，因为每个2操作只会删1个点，所以我们最多会插入 n+q 个点。~~所以要什么重链剖分和线段树暴力就能过~~

实现

我用的是 vector 存储空节点来实现这个过程的。它的好处在于对于1操作删除是 \(O(1)\) 的。不过插入必须用 upper_bound 和 insert 。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=1e5+10;
	int n,Q;
	int fa[maxn][21],rt,dfn[maxn],tot,id[maxn],mn[maxn];
	bool vis[maxn];
	vector<int> q,G[maxn];
	void dfs1(int x){
		mn[x]=x;
		for(int i=0;i<G[x].size();i++)
			dfs1(G[x][i]),mn[x]=min(mn[x],mn[G[x][i]]);
	}
	inline bool cmp1(int a,int b){return mn[a]<mn[b];}
	void dfs(int x){
		for(int i=0;i<20;i++) fa[x][i+1]=fa[fa[x][i]][i];
		sort(G[x].begin(),G[x].end(),cmp1);
		for(int i=0;i<G[x].size();i++)
			dfs(G[x][i]);
		dfn[x]=++tot;
		id[tot]=x;
	}
	inline bool cmp(int a,int b){return dfn[a]>dfn[b];}
	inline void work(){
		n=read(),Q=read();
		for(int i=1;i<=n;i++){
			if((fa[i][0]=read())==0) rt=i;
			G[fa[i][0]].push_back(i);
		}
		dfs1(rt);
		dfs(rt);q.resize(n),q.clear();
		for(int i=n;i;i--) q.push_back(id[i]);
		while(Q--)
		if(read()==1){
			int num=read();
			while(--num)vis[q.back()]=1,q.pop_back();
			printf("%d\n",q.back());
			vis[q.back()]=1;q.pop_back();
		}else{
			int x=read();
			if(!vis[x]){puts("0");continue;}//数据合法，好像没用
			int f=x,ans=0;
			for(int i=20;~i;i--) if(vis[fa[f][i]])f=fa[f][i],ans|=(1<<i);
			vis[f]=0;
			q.insert(upper_bound(q.begin(),q.end(),f,cmp),f);
			printf("%d\n",ans);
		}
	}
}
signed main(){
	star::work();
	return 0;
}

其他

强烈吐槽洛谷的翻译！一直以为是以直接相连节点的编号大小为优先级，结果是子树内的最小值……建议大家看原题面。